# Adapted from "FOV using recursive shadowcasting" by Bjorn Bergstrom.
#
# http://roguebasin.roguelikedevelopment.org/index.php?
# title=PythonShadowcastingImplementation
#
# (The URL should be all on one line, without spaces.)

from wormbane.geometry import Vector

class FieldOfView(object):
    # Multipliers for transforming coordinates to other octants.
    mult = [[1,  0,  0, -1, -1,  0,  0,  1],
            [0,  1, -1,  0,  0, -1,  1,  0],
            [0,  1,  1,  0,  0, -1, -1,  0],
            [1,  0,  0,  1, -1,  0,  0, -1]]

    def __init__(self, level):
        self.level = level
        self.width, self.height = level.size
        self.cells = [[0] * self.width for y in xrange(self.height)]
        self.flag = 0

    def __contains__(self, pos):
        x, y = pos
        return (0 <= x < self.width and 0 <= y < self.height
                and self.cells[y][x] == self.flag)

    def _blocked(self, x, y):
        if x < 0 or y < 0 or x >= self.width or y >= self.height:
            return True
        cell = self.level.cells.get(Vector(x, y))
        return cell.boulder or not cell.feature.passable

    def _add(self, x, y):
        self.cells[y][x] = self.flag
        cell = self.level.cells.get(Vector(x, y))
        if cell:
            self.level.memory[y][x] = (cell.top_item or cell.feature).char

    def _update(self, cx, cy, row, start, end, radius, xx, xy, yx, yy):
        if start < end:
            return
        for j in xrange(row, radius + 1):
            dx, dy = -j - 1, -j
            blocked = False
            while dx <= 0:
                dx += 1

                # l_slope and r_slope store the slopes of the left and right
                # extremities of the square we're considering:
                l_slope, r_slope = ((dx - 0.5) / (dy + 0.5),
                                    (dx + 0.5) / (dy - 0.5))
                if start < r_slope:
                    continue
                elif end > l_slope:
                    break
                else:
                    # Translate the dx, dy coordinates into map coordinates:
                    x, y = cx + dx * xx + dy * xy, cy + dx * yx + dy * yy

                    # Our light beam is touching this square; light it:
                    if dx ** 2 + dy ** 2 < radius ** 2:
                        self._add(x, y)
                    if blocked:
                        # we're scanning a row of blocked squares:
                        if self._blocked(x, y):
                            new_start = r_slope
                            continue
                        else:
                            blocked = False
                            start = new_start
                    else:
                        if self._blocked(x, y) and j < radius:
                            # This is a blocking square, start a child scan:
                            blocked = True
                            self._update(cx, cy, j + 1, start, l_slope, radius,
                                         xx, xy, yx, yy)
                            new_start = r_slope
            # Row is scanned; do next row unless last square was blocked:
            if blocked:
                break

    def update(self, x, y, radius):
        self.flag += 1
        self._add(x, y)
        for oct in range(8):
            self._update(x, y, 1, 1.0, 0.0, radius,
                         self.mult[0][oct], self.mult[1][oct],
                         self.mult[2][oct], self.mult[3][oct])
